
#ifdef a
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void MergeDate(int* arr,int left,int mid,int right,int* temp){
	int begin1, end1, begin2, end2;
	int index = left;
	begin1 = left, end1 = mid;
	begin2 = mid, end2 = right;
	while (begin1 < end1 && begin2 < end2) {
		if (arr[begin1] <= arr[begin2])
			temp[index++] = arr[begin1++];
		else
			temp[index++] = arr[begin2++];
	}
	while(begin1 < end1)
		temp[index++] = arr[begin1++];
	while(begin2 < end2)
		temp[index++] = arr[begin2++];
	return;

}
void MargeSortCricle(int* arr, int size, int* temp) {
	int gap = 1;
	while (gap < size) {
		for (int i = 0; i < size; i += 2 * gap) {
			int left = i;
			int mid = left + gap;
			int right = mid + gap;
			if (mid > size)
				mid = size;
			if (right > size)
				right = size;
			MergeDate(arr, left, mid, right, temp);	
		}
		memcpy(arr, temp, sizeof(arr[0]) * size);
		//每次循环排完一遍后拷贝到arr以进行下次排列
		gap *= 2;
	}
}
void SortPrintf(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
//归并排序非递归
int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int* temp = (int*)malloc(sizeof(int) * size);
	if (!temp)
		return 0;
	MargeSortCricle(arr, size, temp);
	SortPrintf(arr, size);
}
#endif